package com.yun.algorithmproblem.leetcode;

import java.util.*;

public class Leetcode869 {

    // 用静态Map存储：键为数字位数，值为该位数所有2的幂的数字计数数组
    private static final Map<Integer, List<int[]>> powerOf2DigitsMap = new HashMap<>();

    // 静态代码块，在类加载时预处理所有2的幂的数字计数
    static {
        int power = 1; // 2^0 = 1
        for (int i = 0; i <= 30; i++) { // 2^30是不超过1e9的最大2的幂
            int length = String.valueOf(power).length();
            int[] digitCount = countDigits(power);

            // 将当前2的幂的数字计数添加到对应位数的列表中
            powerOf2DigitsMap.computeIfAbsent(length, k -> new ArrayList<>())
                    .add(digitCount);

            // 生成下一个2的幂
            if (i < 30) { // 避免最后一次循环的左移操作导致溢出
                power <<= 1;
            }
        }
    }

    public static void main(String[] args) {
        Leetcode869 obj = new Leetcode869();
        System.out.println(obj.reorderedPowerOf2(1));
    }

    // 统计数字中每个 digit 出现的次数
    private static int[] countDigits(int num) {
        int[] count = new int[10];
        while (num > 0) {
            count[num % 10]++;
            num /= 10;
        }
        return count;
    }

    public boolean reorderedPowerOf2(int n) {
        int length = String.valueOf(n).length();
        int[] targetCount = countDigits(n);

        // 获取相同位数的所有2的幂的数字计数列表
        List<int[]> candidates = powerOf2DigitsMap.getOrDefault(length, Collections.emptyList());

        // 对比是否有匹配的数字计数
        for (int[] candidate : candidates) {
            if (Arrays.equals(candidate, targetCount)) {
                return true;
            }
        }

        return false;
    }
}
